//
// Created by Lenovo on 2025/11/25.
//

#include"ToploSort.h"
#include<stdlib.h>
#include<string.h>
//拓扑排序，表示事情的优先顺序，也可以判断图中是否有环
int TopologicalSort(ArcGraph* graph) {
    int count = 0;
    //要有个入度记录表,也要有个栈，入度为0的点存入栈中
    int* inDegree = static_cast<int *>(malloc(sizeof(int) * graph->nodeNum));
    if(inDegree==NULL) {
        return 0;
    }
    memset(inDegree,0,sizeof(int)*graph->nodeNum);
    int* stack = static_cast<int *>(malloc(sizeof(int) * graph->nodeNum));
    int top = -1;
    if (stack==NULL) {
        free(inDegree);
        return 0;
    }
    //初始化入度记录表
    for (int i = 0; i < graph->nodeNum; i++) {
        if (graph->node[i].firstEdge) {             //i节点有边
            ArcEdge* edge =graph->node[i].firstEdge;
            while (edge) {
                ++inDegree[edge->no];
                edge = edge->next;
            }
        }
    }
    //查找入度记录表，将入度为0的点入栈
    for (int i = 0; i < graph->nodeNum; i++) {
        if (inDegree[i] == 0) {
            stack[++top] = i;
        }
    }
    //循环出栈，弹出第一个任务，并更新入度记录，若为0则存入栈中
    int index = 0;
    while (top != -1) {
        index = stack[top--];
        ++count;
        ArcEdge* edge = graph->node[index].firstEdge;
        while (edge) {                                  //删除出度
            --inDegree[edge->no];
            visitNode(&graph->node[edge->no]);
            if (inDegree[edge->no] == 0) {
                stack[++top] = edge->no;
            }
            edge = edge->next;
        }
    }

    free(inDegree);
    free(stack);
    if (count==graph->nodeNum) {
        return 1;
    }
    else return 0;
    return 0;
}